import java.util.LinkedList;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.RectHV;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;


//
public class KdTree {
    private Node root;

    private class Node {
        private Point2D point2d;
        public Node left;
        public Node right;
        private int size;

        public Node(double x, double y, int size) {
            this.point2d = new Point2D(x, y);
            this.size = size;
        }
    }

    public KdTree() // construct an empty set of points
    {
        root = null;
    }

    // 集合是否为空？
    public boolean isEmpty() // is the set empty?
    {
        return root == null;
    }

    // 集合中的点数
    public int size() // number of points in the set
    {
        if (root == null)
            return 0;
        else
            return size(root);
    }

    private int size(Node node) {
        if (node == null) {
            return 0;
        } else {
            return node.size;
        }
    }

    // 将点添加到集合（如果集合中尚不存在该点）
    public void insert(Point2D p) {
        insert(p.x(), p.y());
    }

    private void insert(double x, double y)// add the point to the set (if it is not already in the set)
    {
        // true用x，反之用y
        root = insert(root, x, y, true);
    }

    private Node insert(Node node, double x, double y, boolean condition) {
        if (node == null)
            return new Node(x, y, 1);

        // 比较一个键值的时候，如果是相等的情况，则先判断是否完全相同，完全相同则返回，不然则大的向右小的向左
        if (condition == true) {
            if (node.point2d.x() != x) {
                if (node.point2d.x() < x)
                    node.right = insert(node.right, x, y, false);
                else if (node.point2d.x() > x)
                    node.left = insert(node.left, x, y, false);
            } else if (node.point2d.x() == x) {
                if (node.point2d.y() == y)
                    return node;
                else if (node.point2d.y() < y)
                    node.right = insert(node.right, x, y, false);
                else
                    node.left = insert(node.left, x, y, false);
            }
        } else {
            if (node.point2d.y() != y) {
                if (node.point2d.y() < y)
                    node.right = insert(node.right, x, y, true);
                else if (node.point2d.y() > y)
                    node.left = insert(node.left, x, y, true);
            } else if (node.point2d.y() == y) {
                if (node.point2d.x() == x)
                    return node;
                else if (node.point2d.x() < x)
                    node.right = insert(node.right, x, y, true);
                else
                    node.left = insert(node.left, x, y, true);
            }
        }

        node.size = 1 + size(node.left) + size(node.right);
        return node;
    }

    // 集合是否包含点 p？
    public boolean contains(Point2D p) // does the set contain point p?
    {
        if (p == null)
            return false;
        Node node = root;
        boolean condition = true;
        double x = p.x();
        double y = p.y();
        while (true) {
            if (node == null) {
                return false;
            }
            if (condition == true) {
                if (Double.compare(node.point2d.x(), x) != 0) {
                    if (Double.compare(node.point2d.x(), x) < 0) {
                        node = node.right;
                        condition = false;
                        continue;
                    } else if (Double.compare(node.point2d.x(), x) > 0) {
                        node = node.left;
                        condition = false;
                        continue;
                    }

                } else if (Double.compare(node.point2d.x(), x) == 0) {
                    if (Double.compare(node.point2d.y(), y) == 0)
                        return true;
                    else if (Double.compare(node.point2d.y(), y) < 0) {
                        node = node.right;
                        condition = false;
                        continue;
                    } else {
                        node = node.left;
                        condition = false;
                        continue;
                    }
                }
            } else {
                if (Double.compare(node.point2d.y(), y) != 0) {
                    if (Double.compare(node.point2d.y(), y) < 0) {
                        node = node.right;
                        condition = true;
                        continue;
                    }

                    else if (Double.compare(node.point2d.y(), y) > 0) {
                        node = node.left;
                        condition = true;
                        continue;
                    }
                } else if (Double.compare(node.point2d.y(), y) == 0) {
                    if (Double.compare(node.point2d.x(), x) == 0)
                        return true;
                    else if (Double.compare(node.point2d.x(), x) < 0) {
                        node = node.right;
                        condition = true;
                        continue;
                    } else {
                        node = node.left;
                        condition = true;
                        continue;
                    }
                }
            }

        }
    }

    // 将所有点绘制为标准绘制
    public void draw() // draw all points to standard draw
    {
        StdDraw.setPenColor(StdDraw.BLACK);
        StdDraw.circle(root.point2d.x(), root.point2d.y(), 0.01);
        StdDraw.setPenColor(StdDraw.RED);
        StdDraw.line(root.point2d.x(), 0, root.point2d.x(), 1);

        draw(root.left, 0, root.point2d.x(), 0, 1, false); // true就是画竖直线，反之画水平线
        draw(root.right, root.point2d.x(), 1, 0, 1, false); // true就是画竖直线，反之画水平线
    }

    private void draw(Node node, double range_x0, double range_x1, double range_y0, double range_y1,
            boolean condition) {
        if (node == null)
            return;
        if (condition == true) {
            StdDraw.setPenColor(StdDraw.BLACK);
            StdDraw.circle(node.point2d.x(), node.point2d.y(), 0.01);
            StdDraw.setPenColor(StdDraw.RED);
            StdDraw.line(node.point2d.x(), range_y0, node.point2d.x(), range_y1);
            draw(node.left, range_x0, node.point2d.x(), range_y0, range_y1, false);
            draw(node.right, node.point2d.x(), range_x1, range_y0, range_y1, false);
        } else {
            StdDraw.setPenColor(StdDraw.BLACK);
            StdDraw.circle(node.point2d.x(), node.point2d.y(), 0.01);
            StdDraw.setPenColor(StdDraw.BLUE);
            StdDraw.line(range_x0, node.point2d.y(), range_x1, node.point2d.y());
            draw(node.left, range_x0, range_x1, range_y0, node.point2d.y(), true);
            draw(node.right, range_x0, range_x1, node.point2d.y(), range_y1, true);
        }
    }

    // 矩形内（或边界上）的所有点
    // 如果查询矩形与对应于节点的矩形不相交，则无需探索该节点（或其子树）。仅当子树可能包含查询矩形中包含的点时，才会搜索子树。
    // 这里直接用边界构建新的矩形，然后调用方法就OK
    // 这里的judge满足再具体判断是否在矩形里，如果search不满足，那么那条子树就不用去看了。
    // 用search遍历
    // condition true就是画竖直线，false就是水平线
    public Iterable<Point2D> range(RectHV rect) // all points that are inside the rectangle (or on the boundary)
    {
        if (isEmpty() == true)
            throw new IllegalArgumentException("calls put() with a null key");
        ;
        LinkedList<Point2D> pointInRec = new LinkedList<Point2D>();
        search(root, rect, pointInRec, true, 0, 1, 0, 1);
        return pointInRec;
    }

    private void search(Node x, RectHV rect, LinkedList<Point2D> pointInRec, boolean condition, double range_x0,
            double range_x1, double range_y0, double range_y1) {
        if (x == null)
            return;
        if (Double.compare(x.point2d.x(), rect.xmax()) <= 0 && Double.compare(x.point2d.x(), rect.xmin()) >= 0
                && Double.compare(x.point2d.y(), rect.ymax()) <= 0 && Double.compare(x.point2d.y(), rect.ymin()) >= 0) {
            Point2D newPoint = new Point2D(x.point2d.x(), x.point2d.y());
            pointInRec.addLast(newPoint);
        }
        if (condition == true) {
            if (judge(rect, range_x0, x.point2d.x(), range_y0, range_y1))// 左子树
            {
                search(x.left, rect, pointInRec, false, range_x0, x.point2d.x(), range_y0, range_y1);
            }
            if (judge(rect, x.point2d.x(), range_x1, range_y0, range_y1))// 右子树
            {
                search(x.right, rect, pointInRec, false, x.point2d.x(), range_x1, range_y0, range_y1);
            }
        } else {
            if (judge(rect, range_x0, range_x1, range_y0, x.point2d.y()))// 左子树
            {
                search(x.left, rect, pointInRec, true, range_x0, range_x1, range_y0, x.point2d.y());
            }
            if (judge(rect, range_x0, range_x1, x.point2d.y(), range_y1))// 右子树
            {
                search(x.right, rect, pointInRec, true, range_x0, range_x1, x.point2d.y(), range_y1);
            }
        }
    }

    private boolean judge(RectHV rect, double range_x0, double range_x1, double range_y0, double range_y1) {
        RectHV range = new RectHV(range_x0, range_y0, range_x1, range_y1);
        if (range.intersects(rect)) {
            return true;
        } else {
            return false;
        }
    }

    // 集合中与点 p 最近的邻居；如果集合为空，则返回 null
    // 从根开始递归搜索
    // 如果迄今为止发现的最近点比查询点与节点对应的矩形之间的距离更近，则无需探索该节点（或其子树）
    // 也就是说，只有当节点可能包含比迄今为止找到的最佳点更近的点时，才搜索该节点
    // 为此，组织递归方法，以便当有两个可能的子树可向下搜索时
    // 始终选择与查询点位于分割线同一侧的子树作为要探索的第一个子树
    // 探索第一个子树时找到的最近点可能就不需要探索第二个子树了
    public Point2D nearest(Point2D p) // a nearest neighbor in the set to point p; null if the set is empty
    {
        if (isEmpty() == true)
            throw new IllegalArgumentException("calls put() with a null key");
        Node pNode = new Node(p.x(), p.y(), 1);
        Node Nearest = new Node(root.point2d.x(), root.point2d.y(), 1);
        Nearest = search_nearest(root, pNode, Nearest, 2, 0, 1, 0, 1, true).Nearest;
        Point2D Nearest_r = new Point2D(Nearest.point2d.x(), Nearest.point2d.y());
        return Nearest_r;
    }

    private class returnPair {
        Node Nearest;
        double minDistance;

        private returnPair(Node Nearest, double minDistance) {
            this.Nearest = Nearest;
            this.minDistance = minDistance;
        }
    }

    private returnPair search_nearest(Node x, Node p, Node Nearest, double minDistance, double range_x0,
            double range_x1, double range_y0, double range_y1, boolean condition) {
        if (x == null)
            return new returnPair(Nearest, minDistance);
        returnPair thisPair = new returnPair(Nearest, minDistance);
        double distance = distanceTo(p, x);
        if (distance < thisPair.minDistance) {
            thisPair.minDistance = distance;
            thisPair.Nearest = x;
        }
        // condition为true左右子树用x分辨，反之用y分辨
        // 外面的if-else判断p在哪个点对应的矩形里，里面的if-else判断是否有必要判断另一边的子树
        // 对于既不在左边也不在右边的子树部分，我们对其子树所在矩形进行判断，如果有可能存在比最小还短的路径，就去探索，如果没可能，那么就不去探索
        if (condition == true) {
            if (p.point2d.x() >= range_x0 && p.point2d.x() <= x.point2d.x() && p.point2d.y() >= range_y0
                    && p.point2d.y() <= range_y1) // 在左边子树对应的矩形里
            {
                thisPair = search_nearest(x.left, p, thisPair.Nearest, thisPair.minDistance, range_x0, x.point2d.x(),
                        range_y0,
                        range_y1, false);

                if (judge_nea(p.point2d, minDistance, x.point2d.x(), range_x1, range_y0, range_y1)) {
                    thisPair = search_nearest(x.right, p, thisPair.Nearest, thisPair.minDistance, x.point2d.x(),
                            range_x1,
                            range_y0, range_y1, false);
                }
            } else if (p.point2d.x() >= x.point2d.x() && p.point2d.x() <= range_x1 && p.point2d.y() >= range_y0
                    && p.point2d.y() <= range_y1) // 在右边子树对应的矩形里
            {
                thisPair = search_nearest(x.right, p, thisPair.Nearest, thisPair.minDistance, x.point2d.x(), range_x1,
                        range_y0,
                        range_y1, false);
                if (judge_nea(p.point2d, minDistance, range_x0, x.point2d.x(), range_y0, range_y1)) {
                    thisPair = search_nearest(x.left, p, thisPair.Nearest, thisPair.minDistance, range_x0,
                            x.point2d.x(),
                            range_y0, range_y1, false);
                }
            } else // 既不在左边里，也不在右边里
            {
                if (judge_nea(p.point2d, minDistance, range_x0, x.point2d.x(), range_y0, range_y1))// 如果左边子树有可能
                {
                    thisPair = search_nearest(x.left, p, thisPair.Nearest, thisPair.minDistance, range_x0,
                            x.point2d.x(),
                            range_y0, range_y1, false);
                }
                if (judge_nea(p.point2d, minDistance, x.point2d.x(), range_x1, range_y0, range_y1))// 如果右边子树有可能
                {
                    thisPair = search_nearest(x.right, p, thisPair.Nearest, thisPair.minDistance, x.point2d.x(),
                            range_x1,
                            range_y0, range_y1, false);
                }
            }
        } else {
            if (p.point2d.x() >= range_x0 && p.point2d.x() <= range_x1 && p.point2d.y() >= range_y0
                    && p.point2d.y() <= x.point2d.y()) // 在左边子树
            {
                thisPair = search_nearest(x.left, p, thisPair.Nearest, thisPair.minDistance, range_x0, range_x1,
                        range_y0, x.point2d.y(), true);
                if (judge_nea(p.point2d, minDistance, range_x0, range_x1, x.point2d.y(), range_y1)) {
                    thisPair = search_nearest(x.right, p, thisPair.Nearest, thisPair.minDistance, range_x0, range_x1,
                            x.point2d.y(), range_y1, true);
                }
            } else if (p.point2d.x() >= range_x0 && p.point2d.x() <= range_x1 && p.point2d.y() >= x.point2d.y()
                    && p.point2d.y() <= range_y1) // 在右边子树
            {
                thisPair = search_nearest(x.right, p, thisPair.Nearest, thisPair.minDistance, range_x0, range_x1,
                        x.point2d.y(),
                        range_y1, true);
                if (judge_nea(p.point2d, minDistance, range_x0, range_x1, range_y0, x.point2d.y())) {
                    thisPair = search_nearest(x.left, p, thisPair.Nearest, thisPair.minDistance, range_x0, range_x1,
                            range_y0, x.point2d.y(), true);
                }
            } else // 既不在左边里，也不在右边里
            {
                if (judge_nea(p.point2d, minDistance, range_x0, range_x1, range_y0, x.point2d.y()))// 如果左边子树有可能
                {
                    thisPair = search_nearest(x.left, p, thisPair.Nearest, thisPair.minDistance, range_x0, range_x1,
                            range_y0, x.point2d.y(), true);
                }
                if (judge_nea(p.point2d, minDistance, range_x0, range_x1, x.point2d.y(), range_y1)) // 如果右边子树有可能
                {
                    thisPair = search_nearest(x.right, p, thisPair.Nearest, thisPair.minDistance, range_x0, range_x1,
                            x.point2d.y(), range_y1, true);
                }
            }
        }
        return thisPair;
    }

    private boolean judge_nea(Point2D p, double minDistance, double range_x0, double range_x1, double range_y0,
            double range_y1) {
        RectHV judge = new RectHV(range_x0, range_y0, range_x1, range_y1);
        return judge.distanceTo(p) < minDistance;
    }

    private double distanceTo(Node tmp1, Node tmp2) {
        double dx = tmp1.point2d.x() - tmp2.point2d.x();
        double dy = tmp1.point2d.y() - tmp2.point2d.y();
        return Math.sqrt(dx * dx + dy * dy);
    }

    public static void main(String[] args) // unit testing of the methods (optional)
    {
        //这里构建的是两个用来测试问题的，一个是用来查找包含点的矩形，一个是用来最近邻搜索的点
        RectHV rectTest = new RectHV(0.25, 0.25, 0.75, 0.75);
        Point2D pTest = new Point2D(0.5, 0.5);

        RectHV rect = new RectHV(0.0, 0.0, 1.0, 1.0);
        rect.draw();
        // StdDraw.line(rectTest.xmin(), rectTest.ymax(), rectTest.xmax(),
        // rectTest.ymax());
        // StdDraw.line(rectTest.xmax(), rectTest.ymin(), rectTest.xmax(),
        // rectTest.ymax());
        // StdDraw.line(rectTest.xmin(), rectTest.ymin(), rectTest.xmax(),
        // rectTest.ymin());
        // StdDraw.line(rectTest.xmin(), rectTest.ymin(), rectTest.xmin(),
        // rectTest.ymax());

        StdDraw.enableDoubleBuffering();
        KdTree kdtree = new KdTree();
        while (true) {
        if (StdDraw.isMousePressed()) {
        double x = StdDraw.mouseX();
        double y = StdDraw.mouseY();
        StdOut.printf("%8.6f %8.6f\n", x, y);
        Point2D p = new Point2D(x, y);
        if (rect.contains(p)) {
        StdOut.printf("%8.6f %8.6f\n", x, y);
        kdtree.insert(p);
        StdDraw.clear();
        kdtree.draw();
        long start = System.nanoTime();
        StdDraw.setPenColor(StdDraw.MAGENTA);
        for(Point2D point:kdtree.range(rectTest))
        {
        StdDraw.circle(point.x(), point.y(), 0.02);
        }
        // StdDraw.line(rectTest.xmin(), rectTest.ymax(), rectTest.xmax(),
        // rectTest.ymax());
        // StdDraw.line(rectTest.xmax(), rectTest.ymin(), rectTest.xmax(),
        // rectTest.ymax());
        // StdDraw.line(rectTest.xmin(), rectTest.ymin(), rectTest.xmax(),
        // rectTest.ymin());
        // StdDraw.line(rectTest.xmin(), rectTest.ymin(), rectTest.xmin(),
        // rectTest.ymax());
        Point2D nearest=kdtree.nearest(pTest);
        StdDraw.setPenColor(StdDraw.BLACK);
        StdDraw.circle(nearest.x(), nearest.y(), 0.05);
        long end = System.nanoTime();
        StdOut.println("run time:"+(end-start)/1e6+"ms");
        StdDraw.show();
        }
        }
        StdDraw.pause(20);
        }

        // // 矩形测试
        // // initialize the data structures from file
        // In in = new In("input.txt");
        // PointSET brute = new PointSET();
        // KdTree kdtree = new KdTree();
        // // long start = System.nanoTime();
        // while (!in.isEmpty()) {
        // double x = in.readDouble();
        // double y = in.readDouble();
        // Point2D p = new Point2D(x, y);
        // kdtree.insert(p);
        // brute.insert(p);
        // }
        // // long mid = System.nanoTime();
        // // StdOut.println("insert time:"+(mid-start)/1e6+"ms");

        // double x0 = 0.0, y0 = 0.0; // initial endpoint of rectangle
        // double x1 = 0.0, y1 = 0.0; // current location of mouse
        // boolean isDragging = false; // is the user dragging a rectangle

        // // draw the points
        // StdDraw.clear();
        // StdDraw.setPenColor(StdDraw.BLACK);
        // StdDraw.setPenRadius(0.01);
        // kdtree.draw();
        // StdDraw.show();
        // // long mid2 = System.nanoTime();
        // // StdOut.println("draw time:"+(mid2-start)/1e6+"ms");

        // // process range search queries
        // StdDraw.enableDoubleBuffering();
        // while (true) {

        // // user starts to drag a rectangle
        // // if (StdDraw.isMousePressed() && !isDragging) {
        // // x0 = x1 = StdDraw.mouseX();
        // // y0 = y1 = StdDraw.mouseY();
        // // isDragging = true;
        // // }

        // // user is dragging a rectangle
        // // else if (StdDraw.isMousePressed() && isDragging) {
        // // x1 = StdDraw.mouseX();
        // // y1 = StdDraw.mouseY();
        // // }

        // // user stops dragging rectangle
        // // else if (!StdDraw.isMousePressed() && isDragging) {
        // // isDragging = false;
        // // }

        // // draw the points
        // StdDraw.clear();
        // StdDraw.setPenColor(StdDraw.BLACK);
        // StdDraw.setPenRadius(0.01);
        // kdtree.draw();

        // // draw the rectangle
        // RectHV rect = new RectHV(0.0, 0.75, 0.5, 0.75);
        // StdDraw.setPenColor(StdDraw.BLACK);
        // StdDraw.setPenRadius();
        // rect.draw();

        // long start2 = System.nanoTime();
        // // draw the range search results for brute-force data structure in red
        // // StdDraw.setPenRadius(0.03);
        // // StdDraw.setPenColor(StdDraw.RED);
        // // for (Point2D p : brute.range(rect))
        // // p.draw();

        // // long mid4 = System.nanoTime();
        // // StdOut.println("pointSet range time:"+(mid4-start2)/1e6+"ms");

        // // long start3 = System.nanoTime();
        // // draw the range search results for kd-tree in blue
        // StdDraw.setPenRadius(0.02);
        // StdDraw.setPenColor(StdDraw.BLUE);
        // for (Point2D p : kdtree.range(rect))
        // p.draw();

        // // long mid3 = System.nanoTime();
        // // StdOut.println("kdtree range time:"+(mid3-start3)/1e6+"ms");
        // StdDraw.show();
        // StdDraw.pause(20);

        // }

        // 最临近点测试
        // initialize the two data structures with point from file
        // In in = new In("input1M.txt");
        // PointSET brute = new PointSET();
        // KdTree kdtree = new KdTree();
        // while (!in.isEmpty()) {
        //     double x = in.readDouble();
        //     double y = in.readDouble();
        //     Point2D p = new Point2D(x, y);
        //     kdtree.insert(p);
        //     brute.insert(p);
        // }

        // // process nearest neighbor queries
        // StdDraw.enableDoubleBuffering();
        // while (true) {

        //     // the location (x, y) of the mouse
        //     double x = StdDraw.mouseX();
        //     double y = StdDraw.mouseY();
        //     Point2D query = new Point2D(x, y);

        //     // draw all of the points
        //     StdDraw.clear();
        //     StdDraw.setPenColor(StdDraw.BLACK);
        //     StdDraw.setPenRadius(0.01);
        //     brute.draw();

        //     // draw in red the nearest neighbor (using brute-force algorithm)
        //     StdDraw.setPenRadius(0.03);
        //     StdDraw.setPenColor(StdDraw.RED);
        //     long start1 = System.nanoTime();
        //     brute.nearest(query).draw();
        //     long start2 = System.nanoTime();
        //     StdDraw.setPenRadius(0.02);
        //     StdOut.println("pointset range time:" + (start2 - start1) / 1e6 + "ms");

        //     // draw in blue the nearest neighbor (using kd-tree algorithm)
        //     StdDraw.setPenColor(StdDraw.BLUE);
        //     long start3 = System.nanoTime();
        //     kdtree.nearest(query).draw();
        //     long start4 = System.nanoTime();
        //     StdOut.println("kdtree range time:" + (start4 - start3) / 1e6 + "ms");
        //     StdDraw.show();
        //     StdDraw.pause(40);
        // }
    }
}
